package com.love.labuladong.twopoint.slidewindow;

/**
 * 1234.替换子串得到平衡字符串
 */
public class BalancedString {



    // Q W E R
    // 0 1 2 3
    // W Q Q R R E
    // 1 0 0 3 3 2
    // cnts[1] = 1 : W 出现一次
    // cnts[0] = 2 : Q 出现一次
    // 就是词频转换
    public static int balancedString(String str){
        int n = str.length();
        int[] arr = new int[n];
        int[] cnts = new int[4];
        for (int i = 0;i < n; i++){
            char c = str.charAt(i);
            arr[i] = c == 'W' ? 1 : (c == 'E' ? 2 : (c == 'R' ? 3 : 0));
            cnts[arr[i]]++;
        }
        // str : 长度是 4 的整数倍，n
        // 每种字符出现的个数 : n/4
        int require = n / 4;
        // 至少要修改多长的子串，才能做到四种字符一样多
        int ans = n;
        // 自由变化的窗口 l ... r
        for (int l = 0, r = 0; l < n; l++) {
            // l ... r : [l, r)
            // l == 0, r == 0 ，窗口0 长度
            // 无 : 不能
            // 0 ... 0 : 不能
            // 0 ... 1 ： 不能
            // ......
            while (!ok(cnts,r-l,require) && r < n){
                // 进入，表示不符合 【窗口之外的四个字符是否都小于等于 n/4】,需要扩大窗口
                // cnts ： 窗口之外的统计
                cnts[arr[r]]--;
                r++;
            }
            // while 跳出
            // 1. l... r-1 [l,r)，做到了
            // 2. r == n,也没做到
            if(ok(cnts,r - l, require)){
                ans = Math.min(ans, r - l);
            }
            // [l,r) : 不被cnts统计到的
            cnts[arr[l]]++;
        }
        return ans;
    }



    // cnts : l ... r 范围上的字符不算！在自由变化的窗口之外，每一种字符的词频统计
    // len : 自由变化窗口的长度
    // require : 每一种字符都要达到的数量
    // 返回值 : 窗口之外的四个字符是否都小于等于 n/4, true : 是
    public static boolean ok(int[] cnts,int len,int require){
        for (int i = 0; i < 4; i++){
            if(cnts[i] > require){
                return false;
            }
            // 假设 ： 一共 20 个字符，则 Q W E R 要各 5 个
            // [不需要修改部分] ： Q : 5, W : 4, E : 1 ,R : 1
            // 此时这个 len == 1 + 4 + 4
            len -= require - cnts[i];
        }
        return len == 0;
    }


    /*************************************** 另一种写法 **********************************************/


    class Solution {
        public int balancedString(String s) {
            int[] counts = new int[26];     // 使用数组来存储四个字符的出现次数（使用数组便于代码书写）
            int len = s.length();   // 字符串长度
            int limit = len / 4;    // n / 4
            char ch;
            // 初始化不替换内容字符出现次数数组，即初始滑动窗口维护一个空串
            for(int i = 0; i < len; i++){
                ch = s.charAt(i);
                counts[ch - 'A']++;
            }
            // 初始化滑动窗口左右指针，维护的子串是[left,right]的内容
            // 初始化子串为空，因此left=0，right=-1表示一个空子串
            int left = 0;
            int right = -1;
            int minLength = len;    // 最小替换子串长度，初始为整个字符串长度
            // 滑动窗口
            while(left < len){
                if(check(counts, limit)){   // 校验通过
                    // 记录当前合法子串的长度并更新最小长度
                    // 左指针右移，那么原本左指针指向的字符就变成不替换的内容，不替换内容多了一个字符，对应count数组中的值加1
                    minLength = Math.min(minLength, right - left + 1);
                    counts[s.charAt(left++) - 'A']++;
                }else if(right < len - 1){
                    // 当前子串不合法且右指针还没到头
                    // 右指针右移，移动后的右指针指向的字符变成了子串的内容，不替换的内容少了一个字符，对应count数组中的值减1
                    counts[s.charAt(++right) - 'A']--;
                }else{
                    // 右指针到头，搜索结束
                    break;
                }
            }
            return minLength;

        }

        /**
         * 校验函数，校验当前counts中四个字符的出现次数是否都小于等于limit；
         * 是返回true，否返回false
         */
        private boolean check(int[] counts, int limit){
            if(counts['Q' - 'A'] > limit || counts['W' - 'A'] > limit || counts['E' - 'A'] > limit || counts['R' - 'A'] > limit){
                return false;
            }
            return true;
        }
    }

}
